Міністерство освіти і науки України
Національний Університет « Львівська Політехніка»
Кафедра ЕОМ
Звіт
до лабораторної роботи №5
на тему: « Структура даних „БІНАРНЕ ДЕРЕВО ПОШУКУ”.»
Варіант 15.
Виконав:
ст. гр. КІ
Львів-2007
Назва роботи: Структури даних “Бінарне дерево пошуку”.
Мета роботи: Закріпити теоретичні знання та оволодіти практичними навиками опрацювання структур даних “Бінарне дерево пошуку”. Засвоїти техніку створення та опрацювання складних типів даних.
Теоретична частина:
Деревом називається множина взаємно-зв’язаних елементів які називаються вузлами розташованих по рівнях. Бінарне дерево- це скінченна множина вузлів кожен з яких або порожній, або складається з кореня пов’язаного з двома різними бінарними деревами які називається лівим і правим піддеревом.
Виконання роботи
Завдання:
Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Виконати обхід дерева у заданому порядку і підрахувати:
кількість вершин дерева, що обраховується при проходженні дерева у прямому порядку;
кількість листків дерева, що обраховується при проходженні дерева у зворотньому порядку;
кількість вузлів, які мають тільки одного нащадка, що обраховується при проходженні дерева у симетричному порядку.
Знайти довжину мінімального шляху між листами.
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct node
{
int data;
struct node *leftson, *rightson;
}*binary_tree;
void Init(binary_tree *root_ptr);
int Empty(binary_tree root);
binary_tree WhoRight(binary_tree tree_node);
void PutLeftLeft(binary_tree tree_node);
binary_tree Who(binary_tree root, int new_data);
void PutRight(binary_tree root, int new_data);
binary_tree Find(binary_tree root, int search_data);
int GoStraight(binary_tree root,int k,int z);
void GoSymmetric(binary_tree root);
void GoReverse(binary_tree root);
binary_tree WhoFather(binary_tree root, binary_tree knot);
binary_tree WhoBrother(binary_tree root, binary_tree knot);
void AddSearchTree(binary_tree *root_ptr, int new_data);
void DeleteSearchTree(binary_tree *root_ptr, int del_data);
void PrintLevel(binary_tree root, int k, int i);
void PrintTurningTree(binary_tree root, int h);
int kil=0;
void main()
{
int z,k=0;
binary_tree t1,p,p1 ;
int x,x1;
unsigned i,n;
Init(&t1);
printf("Enter the number of knots of binary tree: ");
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&x);
AddSearchTree(&t1, x);
};
printf("\n");
kil=0;
k=GoStraight(t1,k,0); //kilkist vyzliv pru priamomy prohodgenni
printf("\nkilkist vyzliv=%d",kil);
printf("\n");
kil=0;
GoSymmetric(t1); //kilkist vyzliv z 1 nashcadkom pru symetru4nomy
z=kil;
printf("\nkilkist vyzliv z 1 nashcadkom=%d",z);
printf("\n");
kil=0;
GoReverse(t1); //kilkist lustkiv pru zvorotniomy
z=kil;
printf("\nkilkist lustkiv=%d",z);
printf("\n");
PrintLevel(t1,20,1);
printf("\n");
puts("vvedit 2 vyzlu:");
scanf("%d%d",&x,&x1);
p=Find(t1,x);
p1=Find(t1,x1);
kil=0;k=0;
while(p!=NULL){
if(p1==p)
break;
while(p1!=NULL){
p1=WhoFather(t1,p1);
kil++;
if(p1==p)
break;
}
if(p1==p)
break;
p1=Find(t1,x1);
p=WhoFather(t1,p);
if(p1==p)
break;
kil=0;
k++;
}
//najmenshuj shliah - najmensha kilkist krokiv dvid 1 vyzla do 2
printf("najmenshuj shliah mig lustkamu = %d",kil+k);
getch();
return;
}
void Init(binary_tree *root_ptr)
{
*root_ptr = NULL;
}
int Empty(binary_tree root)
{
return root == NULL;
}
binary_tree WhoLeft(binary_tree tree_node)
{
if (tree_node)
return tree_node->leftson;
else
return tree_node;
}
binary_tree WhoRight(binary_tree tree_node)
{
if (tree_node)
return tree_node->rightson;
else
return tree_node;
}
binary_tree MakeNode(int new_data)
{
binary_tree new_node;
new_node =(struct node*) malloc(sizeof(struct node));
new_node->data = ...
